{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Execution of All Suffix Instructions Staying in a Grid"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: executeInstructions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #执行所有后缀指令"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>现有一个 <code>n x n</code> 大小的网格，左上角单元格坐标 <code>(0, 0)</code> ，右下角单元格坐标 <code>(n - 1, n - 1)</code> 。给你整数 <code>n</code> 和一个整数数组 <code>startPos</code> ，其中 <code>startPos = [start<sub>row</sub>, start<sub>col</sub>]</code> 表示机器人最开始在坐标为 <code>(start<sub>row</sub>, start<sub>col</sub>)</code> 的单元格上。</p>\n",
    "\n",
    "<p>另给你一个长度为 <code>m</code> 、下标从 <strong>0</strong> 开始的字符串 <code>s</code> ，其中 <code>s[i]</code> 是对机器人的第 <code>i</code> 条指令：<code>'L'</code>（向左移动），<code>'R'</code>（向右移动），<code>'U'</code>（向上移动）和 <code>'D'</code>（向下移动）。</p>\n",
    "\n",
    "<p>机器人可以从 <code>s</code> 中的任一第 <code>i</code> 条指令开始执行。它将会逐条执行指令直到 <code>s</code> 的末尾，但在满足下述条件之一时，机器人将会停止：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>下一条指令将会导致机器人移动到网格外。</li>\n",
    "\t<li>没有指令可以执行。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回一个长度为 <code>m</code> 的数组 <code>answer</code> ，其中 <code>answer[i]</code> 是机器人从第 <code>i</code>&nbsp;条指令 <strong>开始</strong>&nbsp;，可以执行的 <strong>指令数目</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/12/09/1.png\" style=\"width: 145px; height: 142px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3, startPos = [0,1], s = \"RRDDLU\"\n",
    "<strong>输出：</strong>[1,5,4,3,1,0]\n",
    "<strong>解释：</strong>机器人从 startPos 出发，并从第 i 条指令开始执行：\n",
    "- 0: \"<em><strong>R</strong></em>RDDLU\" 在移动到网格外之前，只能执行一条 \"R\" 指令。\n",
    "- 1:  \"<em><strong>RDDLU</strong></em>\" 可以执行全部五条指令，机器人仍在网格内，最终到达 (0, 0) 。\n",
    "- 2:   \"<em><strong>DDLU</strong></em>\" 可以执行全部四条指令，机器人仍在网格内，最终到达 (0, 0) 。\n",
    "- 3:    \"<em><strong>DLU</strong></em>\" 可以执行全部三条指令，机器人仍在网格内，最终到达 (0, 0) 。\n",
    "- 4:     \"<em><strong>L</strong></em>U\" 在移动到网格外之前，只能执行一条 \"L\" 指令。\n",
    "- 5:      \"U\" 如果向上移动，将会移动到网格外。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/12/09/2.png\" style=\"width: 106px; height: 103px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 2, startPos = [1,1], s = \"LURD\"\n",
    "<strong>输出：</strong>[4,1,0,0]\n",
    "<strong>解释：</strong>\n",
    "- 0: \"<em><strong>LURD</strong></em>\"\n",
    "- 1:  \"<em><strong>U</strong></em>RD\"\n",
    "- 2:   \"RD\"\n",
    "- 3:    \"D\"\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/12/09/3.png\" style=\"width: 67px; height: 64px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 1, startPos = [0,0], s = \"LRUD\"\n",
    "<strong>输出：</strong>[0,0,0,0]\n",
    "<strong>解释：</strong>无论机器人从哪条指令开始执行，都会移动到网格外。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == s.length</code></li>\n",
    "\t<li><code>1 &lt;= n, m &lt;= 500</code></li>\n",
    "\t<li><code>startPos.length == 2</code></li>\n",
    "\t<li><code>0 &lt;= start<sub>row</sub>, start<sub>col</sub> &lt; n</code></li>\n",
    "\t<li><code>s</code> 由 <code>'L'</code>、<code>'R'</code>、<code>'U'</code> 和 <code>'D'</code> 组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [execution-of-all-suffix-instructions-staying-in-a-grid](https://leetcode.cn/problems/execution-of-all-suffix-instructions-staying-in-a-grid/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [execution-of-all-suffix-instructions-staying-in-a-grid](https://leetcode.cn/problems/execution-of-all-suffix-instructions-staying-in-a-grid/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3\\n[0,1]\\n\"RRDDLU\"', '2\\n[1,1]\\n\"LURD\"', '1\\n[0,0]\\n\"LRUD\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n",
    "        ans = []\n",
    "        for i in range(len(s)):\n",
    "            temp = startPos[:]\n",
    "            count = 0\n",
    "            for j in range(i, len(s)):\n",
    "                if s[j] == \"R\":\n",
    "                    temp[1] += 1\n",
    "                elif s[j] == \"L\":\n",
    "                    temp[1] -= 1\n",
    "                elif s[j] == \"U\":\n",
    "                    temp[0] -= 1\n",
    "                else:\n",
    "                    temp[0] += 1\n",
    "                \n",
    "                if 0 <= temp[0] < n and 0 <= temp[1] < n:\n",
    "                    count += 1\n",
    "                else:\n",
    "                    break\n",
    "            ans.append(count)\n",
    "        return ans\n",
    "\n",
    "\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n",
    "        m = len(s)\n",
    "        ans = [0] * m\n",
    "        d = {'L':(0, -1), 'R':(0, 1), 'U':(-1, 0), 'D':(1, 0)}\n",
    "        \n",
    "        for i in range(m):\n",
    "            x, y = startPos\n",
    "            cnt = 0\n",
    "            j = i \n",
    "            while j < m:\n",
    "                x, y = x + d[s[j]][0], y + d[s[j]][1]\n",
    "                if 0<=x<n and 0<=y<n:\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    break\n",
    "                j += 1\n",
    "            ans[i] = cnt\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n",
    "        m = len(s)\n",
    "        ans = [0] * m\n",
    "        for i in range(m):\n",
    "            x,y = startPos\n",
    "            cnt = 0\n",
    "            j = i\n",
    "            while j < m:\n",
    "                if s[j] == 'R':\n",
    "                    y += 1\n",
    "                elif s[j] == 'L':\n",
    "                    y -= 1\n",
    "                elif s[j] == 'U':\n",
    "                    x -= 1\n",
    "                else:\n",
    "                    x += 1\n",
    "                if 0<=x<n and 0<=y<n:\n",
    "                    cnt += 1\n",
    "                    j += 1\n",
    "                else:\n",
    "                    break\n",
    "            ans[i] = cnt\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n",
    "        m = len(s)\n",
    "        ans = []\n",
    "        for i in range(m):\n",
    "            x, y = startPos\n",
    "            cnt = m - i\n",
    "            for j in range(i, m):\n",
    "                ch = s[j]\n",
    "                if ch == \"L\":\n",
    "                    y -= 1\n",
    "                elif ch == \"R\":\n",
    "                    y += 1\n",
    "                elif ch == \"U\":\n",
    "                    x -= 1\n",
    "                else:\n",
    "                    x += 1\n",
    "                if x < 0 or x >= n or y < 0 or y >= n:\n",
    "                    cnt = j - i\n",
    "                    break\n",
    "            ans.append(cnt)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOVE = {'R':(1, 0), 'L':(-1, 0), 'U':(0, -1), 'D':(0, 1)}\n",
    "\n",
    "class Solution:\n",
    "    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n",
    "        dx = Counter()\n",
    "        dy = Counter()\n",
    "        ans = [0] * len(s)\n",
    "        # 前往终点\n",
    "        y, x = startPos\n",
    "        for c in s:\n",
    "            x += MOVE[c][0]\n",
    "            y += MOVE[c][1]\n",
    "        # 倒着走\n",
    "        for i, c in enumerate(s[::-1], 1):\n",
    "            # dx与dy是倒着走时最新的来过那个位置的点的序号\n",
    "            dx[x] = dy[y] = i\n",
    "            x -= MOVE[c][0]\n",
    "            y -= MOVE[c][1]\n",
    "            # x1，y1是边界的偏移量，让当前点变为起始点，但是不要移动点，移动边界\n",
    "            x1, y1 = x - startPos[1], y - startPos[0]    \n",
    "            # -1和n是原来的边界，加上偏移量变为新的边界，边界上最新的记录就是第一次越界时的记录\n",
    "            temp = max(dx[x1 - 1], dx[x1 + n], dy[y1 - 1], dy[y1 + n])\n",
    "            # temp为无法到达的点的数量\n",
    "            ans[-i] = i - temp\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n",
    "        answer = []\n",
    "        move = {'L':-1,'U':-1,'R':1,'D':1}  # 方向\n",
    "\n",
    "        for i in range(len(s)):  # 循环len(s)次\n",
    "            cnt = 0\n",
    "            start_row, start_col = startPos[0], startPos[1] # 起始位置\n",
    "\n",
    "            for string in s[i:]:  # 每次读取余下指令\n",
    "                if string=='L' or string=='R':\n",
    "                    start_col = start_col + move.get(string)\n",
    "                elif string=='U' or string=='D':\n",
    "                    start_row = start_row + move.get(string)\n",
    "                \n",
    "                if 0<=start_row<=n-1 and 0<=start_col<=n-1:  \n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "            answer.append(cnt)\n",
    "        \n",
    "        return answer\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mov(self ,n , directions, startPos):\n",
    "        cnt = 0\n",
    "        i, j = startPos[0], startPos[1]\n",
    "        for k in directions:\n",
    "            if k == 'U':\n",
    "                i -= 1\n",
    "            if k == 'D':\n",
    "                i += 1\n",
    "            if k == 'L':\n",
    "                j -= 1\n",
    "            if k == 'R':\n",
    "                j += 1\n",
    "            if 0 <= i <= n-1 and 0 <= j <= n-1:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                return cnt\n",
    "        return cnt\n",
    "    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n",
    "        m = len(s)\n",
    "        ans = [0] * m\n",
    "        for i in range(m):\n",
    "            directions = [s[j] for j in range(i, m)]\n",
    "            ans[i] = self.mov(n, directions, startPos)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "dirs = {'L':(0,-1),'R':(0,1),'U':(-1,0),'D':(1,0)}\n",
    "class Solution:\n",
    "    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n",
    "        LEN = len(s)\n",
    "        res = [0]*LEN\n",
    "\n",
    "        for index in range(LEN):\n",
    "            x,y = startPos\n",
    "            step = 0\n",
    "            for i in range(index, LEN):\n",
    "                dx,dy = dirs[s[i]]\n",
    "                x,y = x+dx, y+dy\n",
    "                if x==n or y==n or x<0 or y<0:\n",
    "                    break\n",
    "                step+=1\n",
    "            res[index] = step\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOVE = {'R':(0, 1), 'L':(0, -1), 'U':(-1, 0), 'D':(1, 0)}\n",
    "\n",
    "class Solution:\n",
    "    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n",
    "        d_x = Counter()\n",
    "        d_y = Counter()\n",
    "        log = []\n",
    "        ans = [0] * len(s)\n",
    "        # 得到最新坐标\n",
    "        y, x = startPos\n",
    "        for c in s:\n",
    "            x += MOVE[c][1]\n",
    "            y += MOVE[c][0]\n",
    "        # 第二次反向遍历求答案\n",
    "        for i, c in enumerate(s[::-1], 1):\n",
    "            d_x[x] = d_y[y] = i\n",
    "            x -= MOVE[c][1]\n",
    "            y -= MOVE[c][0]\n",
    "            # x与y是走到第n-i个时的坐标\n",
    "            # d_x[x坐标],d_y[y坐标]的值为最新到达x/y坐标的命令计数(即执行第n-i个命令时)\n",
    "            x1, y1 = x-startPos[1], y-startPos[0]    # 与初始坐标的差值\n",
    "            temp = max(d_x[x1 - 1], d_x[x1 + n], d_y[y1 - 1], d_y[y1 + n])\n",
    "            ans[-i] = i - temp\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOVE = {'R':(0, 1), 'L':(0, -1), 'U':(-1, 0), 'D':(1, 0)}\n",
    "\n",
    "class Solution:\n",
    "    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n",
    "        d_x, d_y = {}, {}\n",
    "        log = []\n",
    "        ans = [0] * len(s)\n",
    "        # 得到最新坐标\n",
    "        y, x = startPos\n",
    "        for c in s:\n",
    "            x += MOVE[c][1]\n",
    "            y += MOVE[c][0]\n",
    "        # 第二次反向遍历求答案\n",
    "        for i, c in enumerate(s[::-1], 1):\n",
    "            d_x[x] = d_y[y] = i\n",
    "            x -= MOVE[c][1]\n",
    "            y -= MOVE[c][0]\n",
    "            # x与y是走到第n-i个时的坐标\n",
    "            # d_x[x坐标],d_y[y坐标]的值为最新到达x/y坐标的命令计数(即执行第n-i个命令时)\n",
    "            a = i\n",
    "            x1, y1 = x-startPos[1], y-startPos[0]    # 与初始坐标的差值\n",
    "            temp = 0\n",
    "            if x1 - 1 in d_x:\n",
    "                temp = max(temp, d_x[x1 - 1])\n",
    "            if x1 + n in d_x:\n",
    "                temp = max(temp, d_x[x1 + n])\n",
    "            if y1 - 1 in d_y:\n",
    "                temp = max(temp, d_y[y1 - 1])\n",
    "            if y1 + n in d_y:\n",
    "                temp = max(temp, d_y[y1 + n])\n",
    "            a -= temp\n",
    "            ans[-i] = a\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n",
    "        res = []\n",
    "        for i in range(len(s)):\n",
    "            j = i\n",
    "            x, y = startPos[1], startPos[0]\n",
    "            while j < len(s):\n",
    "                if s[j] == 'R':\n",
    "                    x += 1\n",
    "                elif s[j] == 'L':\n",
    "                    x -= 1\n",
    "                elif s[j] == 'U':\n",
    "                    y -= 1\n",
    "                elif s[j] == 'D':\n",
    "                    y += 1\n",
    "                if x < 0 or x >= n or y < 0 or y >= n:\n",
    "                    res.append(j - i)\n",
    "                    break\n",
    "                else:\n",
    "                    j += 1\n",
    "            else:\n",
    "                res.append(j - i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n",
    "        ans = []\n",
    "        m = len(s)\n",
    "        for i in range(m):\n",
    "            temp = 0\n",
    "            pos = startPos[:]\n",
    "            for j in range(i, m):\n",
    "                if s[j] == 'L':\n",
    "                    pos[1] -= 1\n",
    "                elif s[j] == 'R':\n",
    "                    pos[1] += 1\n",
    "                elif s[j] == 'U':\n",
    "                    pos[0] -= 1\n",
    "                else:\n",
    "                    pos[0] += 1\n",
    "                if not (0 <= pos[0] < n and 0 <= pos[1] < n):\n",
    "                    break\n",
    "                else:\n",
    "                    temp += 1\n",
    "            ans.append(temp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n",
    "        ans, d = [], {'U' : (-1, 0), 'D' : (1, 0), 'L' : (0, -1), 'R' : (0, 1)}\n",
    "        while s:\n",
    "            px, py = startPos\n",
    "            for i, c in enumerate(s):\n",
    "                px += d[c][0]\n",
    "                py += d[c][1]\n",
    "                if px < 0 or px >= n or py < 0 or py >= n: break\n",
    "            else: i += 1\n",
    "            ans.append(i)\n",
    "            s = s[1:]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n",
    "        ans = [0] * len(s) \n",
    "        for i in range(len(s)):\n",
    "            x, y = startPos\n",
    "            for c in s[i:]:\n",
    "                if c == 'L':\n",
    "                    x, y = x, y-1\n",
    "                elif c == 'R':\n",
    "                    x, y = x, y+1\n",
    "                elif c == 'U':\n",
    "                    x, y = x-1, y\n",
    "                else:\n",
    "                    x, y = x+1, y\n",
    "                if 0<=x<n and 0<=y<n:\n",
    "                    #print(i, x, y)\n",
    "                    ans[i]+=1\n",
    "                else:\n",
    "                    break \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def check(pos, s):\n",
    "\n",
    "        return \n",
    "\n",
    "    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n",
    "        res = []\n",
    "        for i in range(len(s)):\n",
    "            pos = startPos\n",
    "            current = 0\n",
    "            for j in range(len(s) - i):\n",
    "                if s[i+j] == 'U':\n",
    "                    pos = [pos[0] - 1, pos[1]]\n",
    "                if s[i+j] == 'D':\n",
    "                    pos = [pos[0] + 1, pos[1]]\n",
    "                if s[i+j] == 'L':\n",
    "                    pos = [pos[0], pos[1] - 1]\n",
    "                if s[i+j] == 'R':\n",
    "                    pos = [pos[0], pos[1] + 1]\n",
    "                if min(pos) < 0 or max(pos) >= n:\n",
    "                    break;\n",
    "                current = j+1\n",
    "            res.append(current)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n",
    "        MOVE = {'R':(0, 1), 'L':(0, -1), 'U':(-1, 0), 'D':(1, 0)}\n",
    "        ans = [0] * len(s)\n",
    "        for i in range(len(s)):\n",
    "            now = startPos.copy()\n",
    "            for c in s[i:]:\n",
    "                row, col = MOVE[c]\n",
    "                now[0] += row\n",
    "                now[1] += col\n",
    "                if now[1] < 0 or now[1] >= n or now[0] < 0 or now[0] >= n:\n",
    "                    break\n",
    "                ans[i] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n",
    "        res = []\n",
    "        for i in range(len(s)):\n",
    "            x0,y0 = startPos[0],startPos[1]\n",
    "            j = i\n",
    "            while j < len(s):\n",
    "                if s[j] == 'L':\n",
    "                    y0 -= 1\n",
    "                if s[j] == 'R':\n",
    "                    y0 += 1\n",
    "                if s[j] == 'U':\n",
    "                    x0 -= 1\n",
    "                if s[j] == 'D':\n",
    "                    x0 += 1\n",
    "                if x0<0 or x0>=n or y0<0 or y0>=n:\n",
    "                    break\n",
    "                else:\n",
    "                    j += 1\n",
    "            res.append(j-i)\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n",
    "        m = len(s)\n",
    "        ans = [0]*m\n",
    "        finalPos = [-1,-1]\n",
    "        for i in range(m):\n",
    "            currentPos = startPos.copy()\n",
    "            depth = 0\n",
    "            while depth< m-i:\n",
    "                move = s[i+depth]\n",
    "                if move == \"R\":\n",
    "                    currentPos[1] += 1\n",
    "                if move == \"L\":\n",
    "                    currentPos[1] -= 1\n",
    "                if move == \"U\":\n",
    "                    currentPos[0] -= 1\n",
    "                if move == \"D\":\n",
    "                    currentPos[0] += 1\n",
    "                if (currentPos[0]>-1)&(currentPos[0]<n)&(currentPos[1]>-1)&(currentPos[1]<n):\n",
    "                    depth += 1\n",
    "                else:\n",
    "                    break\n",
    "            ans[i] = depth\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "dirs = {'L':(0,-1),'R':(0,1),'U':(-1,0),'D':(1,0)}\n",
    "class Solution:\n",
    "    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n",
    "        LEN = len(s)\n",
    "        res = [0]*LEN\n",
    "\n",
    "        for index in range(LEN):\n",
    "            x,y = startPos\n",
    "            step = 0\n",
    "            for i in range(index, LEN):\n",
    "                dx,dy = dirs[s[i]]\n",
    "                x,y = x+dx, y+dy\n",
    "                if x==n or y==n or x<0 or y<0:\n",
    "                    break\n",
    "                step+=1\n",
    "            res[index] = step\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n",
    "        ans = []\n",
    "        for i in range(len(s)):\n",
    "            x, y = startPos\n",
    "            cnt = len(s) - i\n",
    "            for j in range(i,len(s)):\n",
    "                if s[j] == 'R':\n",
    "                    y += 1\n",
    "                elif s[j] == 'L':\n",
    "                    y -= 1\n",
    "                elif s[j] == 'U':\n",
    "                    x -= 1\n",
    "                else:\n",
    "                    x += 1\n",
    "                if x < 0 or x >= n or y < 0 or y >= n:\n",
    "                    cnt = j - i\n",
    "                    break\n",
    "            ans.append(cnt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n",
    "        res = []\n",
    "        for i in range(len(s)):\n",
    "            x0,y0 = startPos[0],startPos[1]\n",
    "            j = i\n",
    "            while j < len(s):\n",
    "                if s[j] == 'L':\n",
    "                    y0 -= 1\n",
    "                if s[j] == 'R':\n",
    "                    y0 += 1\n",
    "                if s[j] == 'U':\n",
    "                    x0 -= 1\n",
    "                if s[j] == 'D':\n",
    "                    x0 += 1\n",
    "                if x0<0 or x0>=n or y0<0 or y0>=n:\n",
    "                    break\n",
    "                else:\n",
    "                    j += 1\n",
    "            res.append(j-i)\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n",
    "        返回数组 = []\n",
    "        append = 返回数组.append\n",
    "        for i in range(len(s)):\n",
    "            步数 = 0\n",
    "            y, x = startPos\n",
    "            for j in s[i:]:\n",
    "                match j:\n",
    "                    case \"R\":\n",
    "                        x += 1\n",
    "                        if x == n:\n",
    "                            break\n",
    "                    case \"L\":\n",
    "                        x -= 1\n",
    "                        if x < 0:\n",
    "                            break\n",
    "                    case \"D\":\n",
    "                        y += 1\n",
    "                        if y == n:\n",
    "                            break\n",
    "                    case \"U\":\n",
    "                        y -= 1\n",
    "                        if y < 0:\n",
    "                            break\n",
    "                步数 += 1\n",
    "            append(步数)\n",
    "        return 返回数组"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOVE = {'R':(0, 1), 'L':(0, -1), 'U':(-1, 0), 'D':(1, 0)}\n",
    "\n",
    "class Solution:\n",
    "    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n",
    "        d_x, d_y, len_s = {}, {}, len(s)\n",
    "        log, ans = [], [0] * len_s\n",
    "        # 得到最新坐标\n",
    "        y, x = startPos\n",
    "        for c in s:\n",
    "            x += MOVE[c][1]\n",
    "            y += MOVE[c][0]\n",
    "        # 第二次反向遍历求答案\n",
    "        for i, c in enumerate(s[::-1], 1):\n",
    "            d_x[x] = d_y[y] = i\n",
    "            x -= MOVE[c][1]\n",
    "            y -= MOVE[c][0]\n",
    "            # x与y是走到第n-i个时的坐标，d_x[x坐标],d_y[y坐标]的值为最新到达x/y坐标的命令计数(即执行第n-i个命令时)\n",
    "            a = i\n",
    "            x1, y1 = x-startPos[1], y-startPos[0]    # 与初始坐标的差值\n",
    "            if x1 - 1 in d_x:\n",
    "                a = min(a, i - d_x[x1 - 1])\n",
    "            if x1 + n in d_x:\n",
    "                a = min(a, i - d_x[x1 + n])\n",
    "            if y1 - 1 in d_y:\n",
    "                a = min(a, i - d_y[y1 - 1])\n",
    "            if y1 + n in d_y:\n",
    "                a = min(a, i - d_y[y1 + n])\n",
    "            ans[- i] = a\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n",
    "        ans = []\n",
    "        move = {\"R\":[0,1],\"L\":[0,-1],\"U\":[-1,0],\"D\":[1,0]}\n",
    "        while s:\n",
    "            x = startPos[0]\n",
    "            y = startPos[1]\n",
    "            for i, j in enumerate(s):\n",
    "                x +=  + move[j][0]\n",
    "                y += move[j][1]\n",
    "                if (x==-1)or (x==n) or(y==-1)or (y==n):\n",
    "                    break\n",
    "                else:\n",
    "                    i += 1 \n",
    "            ans.append(i)\n",
    "            s = s[1:]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOVE = {'R':(1, 0), 'L':(-1, 0), 'U':(0, -1), 'D':(0, 1)}\n",
    "class Solution:\n",
    "    def mov(self ,n , directions, startPos):\n",
    "        cnt = 0\n",
    "        i, j = startPos[0], startPos[1]\n",
    "        for k in directions:\n",
    "            i += MOVE[k][1]\n",
    "            j += MOVE[k][0]\n",
    "            if 0 <= i <= n-1 and 0 <= j <= n-1:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                return cnt\n",
    "        return cnt\n",
    "    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n",
    "        m = len(s)\n",
    "        ans = [0] * m\n",
    "        for i in range(m):\n",
    "            directions = [s[j] for j in range(i, m)]\n",
    "            ans[i] = self.mov(n, directions, startPos)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n",
    "        hash = {\"L\":[0,-1],\"R\":[0,1], \"U\":[-1,0], \"D\":[1,0]}\n",
    "        res = []\n",
    "        if n==1:\n",
    "            return [0 for c in s]\n",
    "        for i in range(len(s)):\n",
    "            pos=list(startPos) \n",
    "            cnt=0\n",
    "            for j in range(i,len(s)):\n",
    "                pos[0] += hash[s[j]][0]\n",
    "                pos[1] += hash[s[j]][1]\n",
    "                if 0<=pos[0]<=n-1 and 0<=pos[1]<=n-1:\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    break\n",
    "            res.append(cnt)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n",
    "        a,b = startPos\n",
    "        D = {'L':b,'R':n-b-1,'U':a,'D':n-a-1}\n",
    "        l = len(s)\n",
    "        Res = []\n",
    "        for i in range(l):\n",
    "            TD = Counter()\n",
    "            for temp in range(i,l):\n",
    "                c = s[temp]\n",
    "                if c == 'L':\n",
    "                    if 'R' in TD and TD['R'] > 0:TD['R'] -= 1\n",
    "                    else:TD['L'] += 1\n",
    "                elif c == 'R':\n",
    "                    if 'L' in TD and TD['L'] > 0:TD['L'] -= 1\n",
    "                    else:TD['R'] += 1\n",
    "                elif c == 'U':\n",
    "                    if 'D' in TD and TD['D'] > 0:TD['D'] -= 1\n",
    "                    else:TD['U'] += 1\n",
    "                else:\n",
    "                    if 'U' in TD and TD['U'] > 0:TD['U'] -= 1\n",
    "                    else:TD['D'] += 1\n",
    "                flag = 1\n",
    "                for x in ('L','R','U','D'):\n",
    "                    if D[x] < TD[x]:\n",
    "                        Res.append(temp-i)\n",
    "                        flag = 0\n",
    "                        break\n",
    "                if not flag:break\n",
    "            if flag:Res.append(l-i)\n",
    "        return Res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n",
    "        \n",
    "        m=len(s)\n",
    "        ans=[0]*m\n",
    "        for i in range(m):\n",
    "            tmp=s[i:]\n",
    "            cnt=0\n",
    "            x,y=startPos\n",
    "            for r in tmp:\n",
    "                if r==\"R\":\n",
    "                    y=y+1\n",
    "                    if y>=n:\n",
    "                        break\n",
    "                    cnt+=1\n",
    "                elif r==\"L\":\n",
    "                    y=y-1\n",
    "                    if y<0:\n",
    "                        break\n",
    "                    cnt+=1\n",
    "                elif r==\"D\":\n",
    "                    x=x+1\n",
    "                    if x>=n:\n",
    "                        break\n",
    "                    cnt+=1\n",
    "                elif r==\"U\":\n",
    "                    x=x-1\n",
    "                    if x<0:\n",
    "                        break\n",
    "                    cnt+=1\n",
    "            ans[i]=cnt\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n",
    "        m = len(s)\n",
    "        ans = [0]*m\n",
    "        for i in range(m):\n",
    "            currentPos = startPos.copy()\n",
    "            depth = 0\n",
    "            while depth< m-i:\n",
    "                move = s[i+depth]\n",
    "                if move == \"R\":\n",
    "                    currentPos[1] += 1\n",
    "                if move == \"L\":\n",
    "                    currentPos[1] -= 1\n",
    "                if move == \"U\":\n",
    "                    currentPos[0] -= 1\n",
    "                if move == \"D\":\n",
    "                    currentPos[0] += 1\n",
    "                if (currentPos[0]==-1)or (currentPos[0]==n) or(currentPos[1]==-1)or (currentPos[1]==n):\n",
    "                    break\n",
    "                else:\n",
    "                    depth += 1\n",
    "            ans[i] = depth\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n",
    "        m = len(s)\n",
    "        record = [[0, 0] for _ in range(m+1)]\n",
    "        for i in range(1, m+1):\n",
    "            if s[i-1] == 'R':\n",
    "                record[i][1] = record[i-1][1] + 1\n",
    "                record[i][0] = record[i-1][0]\n",
    "            elif s[i-1] == 'L':\n",
    "                record[i][1] = record[i-1][1] - 1\n",
    "                record[i][0] = record[i-1][0]\n",
    "            elif s[i-1] == 'D':\n",
    "                record[i][0] = record[i-1][0] + 1\n",
    "                record[i][1] = record[i-1][1]\n",
    "            else:\n",
    "                record[i][0] = record[i-1][0] - 1\n",
    "                record[i][1] = record[i-1][1]\n",
    "        \n",
    "        res = [0 for _ in range(m)]\n",
    "        # print(record, n)\n",
    "        for i in range(m):\n",
    "            j = i+1\n",
    "            while j < m+1:\n",
    "                x, y = record[j][0] - record[i][0] +startPos[0], record[j][1] - record[i][1] + startPos[1]\n",
    "                # print(x, y, 0 <= x < n, 0 <= y < n)\n",
    "                # print(j, i)\n",
    "                if not (0 <= x < n and 0 <= y < n):\n",
    "                    break\n",
    "                else:\n",
    "                    res[i] = j-i\n",
    "                    j += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "dirs = {'L':(0,-1),'R':(0,1),'U':(-1,0),'D':(1,0)}\n",
    "class Solution:\n",
    "    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n",
    "        LEN = len(s)\n",
    "        res = [0]*LEN\n",
    "\n",
    "        for index in range(LEN):\n",
    "            x,y = startPos\n",
    "            step = 0\n",
    "            for i in range(index, LEN):\n",
    "                dx,dy = dirs[s[i]]\n",
    "                x,y = x+dx, y+dy\n",
    "                if x==n or y==n or x<0 or y<0:\n",
    "                    break\n",
    "                step+=1\n",
    "            res[index] = step\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOVE = {'R':(0, 1), 'L':(0, -1), 'U':(-1, 0), 'D':(1, 0)}\n",
    "class Solution:\n",
    "    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n",
    "        d_x,d_y,len_s = {},{},len(s)\n",
    "        y,x = startPos\n",
    "        log,ans = [],[0]*len_s\n",
    "        #得到最新坐标\n",
    "        for c in s:\n",
    "            x += MOVE[c][1]\n",
    "            y += MOVE[c][0]\n",
    "        #第二次遍历反向求答案\n",
    "        for i, c in enumerate(s[::-1],1):\n",
    "            d_x[x],d_y[y] = i,i\n",
    "            x -= MOVE[c][1]\n",
    "            y -= MOVE[c][0]\n",
    "            #x与y是走到第n-i个时的坐标，d_x[x坐标],d_y[y坐标]的值为最新到达x/y坐标的命令计数(即执行第n-i个命令时)\n",
    "            a = i\n",
    "            x1,y1 = x-startPos[1],y-startPos[0]\n",
    "            if -1+x1 in d_x:\n",
    "                a = min(a,i-d_x[-1+x1])\n",
    "            if n+x1 in d_x:\n",
    "                a = min(a,i-d_x[n+x1])\n",
    "            if -1+y1 in d_y:\n",
    "                a = min(a,i-d_y[-1+y1])\n",
    "            if n+y1 in d_y:\n",
    "                a = min(a,i-d_y[n+y1])\n",
    "            ans[len_s-i] = a\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOVE = {'R':(1, 0), 'L':(-1, 0), 'U':(0, -1), 'D':(0, 1)}\n",
    "\n",
    "class Solution:\n",
    "    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n",
    "        y, x = startPos\n",
    "        for c in s:\n",
    "            x += MOVE[c][0]\n",
    "            y += MOVE[c][1]\n",
    "\n",
    "        ans = [0] * len(s)\n",
    "        dx, dy = Counter(), Counter()\n",
    "        for i, c in enumerate(s[::-1], 1):\n",
    "            dx[x] = dy[y] = i\n",
    "            x -= MOVE[c][0]\n",
    "            y -= MOVE[c][1]\n",
    "            x1, y1 = x - startPos[1], y - startPos[0]    \n",
    "            ans[-i] = i - max(dx[x1 - 1], dx[x1 + n], dy[y1 - 1], dy[y1 + n])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOVE = {'R':(0, 1), 'L':(0, -1), 'U':(-1, 0), 'D':(1, 0)}\n",
    "\n",
    "class Solution:\n",
    "    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n",
    "        d_x = defaultdict(int)\n",
    "        d_y = defaultdict(int)\n",
    "        log = []\n",
    "        ans = [0] * len(s)\n",
    "        # 得到最新坐标\n",
    "        y, x = startPos\n",
    "        for c in s:\n",
    "            x += MOVE[c][1]\n",
    "            y += MOVE[c][0]\n",
    "        # 第二次反向遍历求答案\n",
    "        for i, c in enumerate(s[::-1], 1):\n",
    "            d_x[x] = d_y[y] = i\n",
    "            x -= MOVE[c][1]\n",
    "            y -= MOVE[c][0]\n",
    "            # x与y是走到第n-i个时的坐标\n",
    "            # d_x[x坐标],d_y[y坐标]的值为最新到达x/y坐标的命令计数(即执行第n-i个命令时)\n",
    "            x1, y1 = x-startPos[1], y-startPos[0]    # 与初始坐标的差值\n",
    "            temp = max(d_x[x1 - 1], d_x[x1 + n], d_y[y1 - 1], d_y[y1 + n])\n",
    "            ans[-i] = i - temp\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def executeInstructions(self, n: int, startPos: [int], s: str) -> [int]:\n",
    "        # 上、右、下、左\n",
    "        ans=list()\n",
    "        for p in range(len(s)):\n",
    "            xx=startPos[0]\n",
    "            yy=startPos[1]\n",
    "            cur=p-1\n",
    "            while 0<=xx<n and 0<=yy<n and cur<len(s)-1:\n",
    "                cur+=1\n",
    "                if s[cur]=='L': yy-=1\n",
    "                elif s[cur]=='R': yy+=1\n",
    "                elif s[cur]=='U': xx-=1\n",
    "                else: xx+=1\n",
    "\n",
    "            if 0<=xx<n and 0<=yy<n:\n",
    "                ans.append(cur-p+1)\n",
    "            else:\n",
    "                ans.append(cur-p)\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n",
    "        rslt = []\n",
    "        for ix in range(len(s)):\n",
    "\n",
    "            st_ix = ix\n",
    "            cnt = 0\n",
    "            tx, ty = startPos\n",
    "            while st_ix < len(s):\n",
    "                nx, ny = tx, ty\n",
    "                if s[st_ix] == 'L':\n",
    "                    ny -= 1\n",
    "                elif s[st_ix] == 'R':\n",
    "                    ny += 1\n",
    "                elif s[st_ix] == 'U':\n",
    "                    nx -= 1\n",
    "                else:\n",
    "                    nx += 1\n",
    "                if nx < 0 or nx >= n or ny < 0 or ny >= n:\n",
    "                    break\n",
    "                cnt += 1\n",
    "                tx, ty = nx, ny\n",
    "                st_ix += 1\n",
    "            rslt.append(cnt)\n",
    "        return rslt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n",
    "        dirs = {\n",
    "            'R': (0, 1),\n",
    "            'L': (0, -1),\n",
    "            'D': (1, 0),\n",
    "            'U': (-1, 0),\n",
    "        }\n",
    "        k = len(s)\n",
    "        ret = list(range(k, 0, -1))\n",
    "        for i in range(k):\n",
    "            x, y = startPos\n",
    "            for j in range(i, k):\n",
    "                x += dirs[s[j]][0]\n",
    "                y += dirs[s[j]][1]\n",
    "                if x < 0 or x >= n or y < 0 or y >= n:\n",
    "                    ret[i] = j - i\n",
    "                    break\n",
    "        return ret\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n",
    "        ans, d = [], {'U' : (-1, 0), 'D' : (1, 0), 'L' : (0, -1), 'R' : (0, 1)}\n",
    "        while s:\n",
    "            px, py = startPos\n",
    "            for i, c in enumerate(s):\n",
    "                px += d[c][0]\n",
    "                py += d[c][1]\n",
    "                if px < 0 or px >= n or py < 0 or py >= n: break\n",
    "            else: i += 1\n",
    "            ans.append(i)\n",
    "            s = s[1:]\n",
    "        return ans        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def executeInstructions(self, n, startPos, s):\n",
    "        ans, d = [], {'U' : (-1, 0), 'D' : (1, 0), 'L' : (0, -1), 'R' : (0, 1)}\n",
    "        while s:\n",
    "            px, py = startPos\n",
    "            for i, c in enumerate(s):\n",
    "                px += d[c][0]\n",
    "                py += d[c][1]\n",
    "                if px < 0 or px >= n or py < 0 or py >= n: break\n",
    "            else: i += 1\n",
    "            ans.append(i)\n",
    "            s = s[1:]\n",
    "        return ans        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOVE = {'R':(0, 1), 'L':(0, -1), 'U':(-1, 0), 'D':(1, 0)}\n",
    "\n",
    "class Solution:\n",
    "    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n",
    "        dx = Counter()\n",
    "        dy = Counter()\n",
    "        log = []\n",
    "        ans = [0] * len(s)\n",
    "        # 前往终点\n",
    "        y, x = startPos\n",
    "        for c in s:\n",
    "            x += MOVE[c][1]\n",
    "            y += MOVE[c][0]\n",
    "        # 倒着走\n",
    "        for i, c in enumerate(s[::-1], 1):\n",
    "            # dx与dy\n",
    "            dx[x] = dy[y] = i\n",
    "            x -= MOVE[c][1]\n",
    "            y -= MOVE[c][0]\n",
    "            # x与y是走到第n-i个时的坐标\n",
    "            # d_x[x坐标],d_y[y坐标]的值为最新到达x/y坐标的命令计数(即执行第n-i个命令时)\n",
    "            x1, y1 = x-startPos[1], y-startPos[0]    # 与初始坐标的差值\n",
    "            temp = max(dx[x1 - 1], dx[x1 + n], dy[y1 - 1], dy[y1 + n])\n",
    "            # temp为无法到达的点的数量\n",
    "            ans[-i] = i - temp\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n",
    "        result, m, d = [], len(s), dict(R=(0, 1), L=(0, -1), U=(-1, 0), D=(1, 0))\n",
    "        for i in range(m):\n",
    "            j, y, x = i, *startPos\n",
    "            while j < m:\n",
    "                x += d[s[j]][1]\n",
    "                y += d[s[j]][0]\n",
    "                if not (0 <= x < n and 0 <= y < n):\n",
    "                    break\n",
    "                j += 1\n",
    "            result.append(j - i)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n",
    "        ans = []\n",
    "        currentPos = [0,0]\n",
    "        move = {\"R\":[0,1],\"L\":[0,-1],\"U\":[-1,0],\"D\":[1,0]}\n",
    "        while s:\n",
    "            currentPos[0] = startPos[0]\n",
    "            currentPos[1] = startPos[1]\n",
    "            for i, j in enumerate(s):\n",
    "                currentPos[0] = currentPos[0] + move[j][0]\n",
    "                currentPos[1] = currentPos[1] + move[j][1]\n",
    "                if (currentPos[0]==-1)or (currentPos[0]==n) or(currentPos[1]==-1)or (currentPos[1]==n):\n",
    "                    break\n",
    "                else:\n",
    "                    i += 1 \n",
    "            ans.append(i)\n",
    "            s = s[1:]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n",
    "        m = len(s)\n",
    "        ind = {\"L\": [0, -1], \"R\": [0, 1], \"U\": [-1, 0], \"D\": [1, 0]}\n",
    "        ans = []\n",
    "        for i in range(m):\n",
    "            x, y = startPos[:]\n",
    "            for j in range(i, m):\n",
    "                a, b = ind[s[j]]\n",
    "                x += a\n",
    "                y += b\n",
    "                if not (0<=x<n and 0<=y<n):\n",
    "                    ans.append(j-i)\n",
    "                    break\n",
    "            else:\n",
    "                ans.append(m-i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n",
    "        answer = []\n",
    "        directions = {'L': (0, -1), 'R': (0, 1), 'U': (-1, 0), 'D': (1, 0)}\n",
    "        \n",
    "        for i in range(len(s)):\n",
    "            # 初始化机器人的起始位置和能执行的指令数\n",
    "            x, y = startPos\n",
    "            count = 0\n",
    "            \n",
    "            for j in range(i, len(s)):\n",
    "                dx, dy = directions[s[j]]\n",
    "                # 计算新位置\n",
    "                new_x, new_y = x + dx, y + dy\n",
    "                \n",
    "                # 检查新位置是否在网格内\n",
    "                if 0 <= new_x < n and 0 <= new_y < n:\n",
    "                    x, y = new_x, new_y\n",
    "                    count += 1\n",
    "                else:\n",
    "                    break\n",
    "            \n",
    "            answer.append(count)\n",
    "        \n",
    "        return answer\n",
    "\n",
    "# 测试代码\n",
    "sol = Solution()\n",
    "print(sol.executeInstructions(3, [0, 0], 'RRD'))  # 应输出 [3, 2, 1]\n",
    "print(sol.executeInstructions(5, [2, 3], 'LRUD'))  # 应输出 [4, 4, 3, 2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n",
    "        返回数组 = []\n",
    "        append = 返回数组.append\n",
    "        for i in range(len(s)):\n",
    "            步数 = 0\n",
    "            y, x = startPos\n",
    "            for j in s[i:]:\n",
    "                match j:\n",
    "                    case \"R\":\n",
    "                        x += 1\n",
    "                        if x == n:\n",
    "                            break\n",
    "                    case \"L\":\n",
    "                        x -= 1\n",
    "                        if x < 0:\n",
    "                            break\n",
    "                    case \"D\":\n",
    "                        y += 1\n",
    "                        if y == n:\n",
    "                            break\n",
    "                    case \"U\":\n",
    "                        y -= 1\n",
    "                        if y < 0:\n",
    "                            break\n",
    "                步数 += 1\n",
    "            append(步数)\n",
    "        return 返回数组"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n",
    "        def cal(startPos, n, s):\n",
    "            count = 0\n",
    "            r, c = startPos\n",
    "            for ch in s:\n",
    "                new_r, new_c = r+directions[ch][0], c+directions[ch][1]\n",
    "                if 0 <= new_r < n and 0 <= new_c < n:\n",
    "                    r, c = new_r, new_c\n",
    "                    count += 1\n",
    "                else:\n",
    "                    break\n",
    "            return count\n",
    "        \n",
    "        res = []\n",
    "        directions = {\n",
    "            'L': (0, -1),\n",
    "            'R': (0, 1),\n",
    "            'U': (-1, 0),\n",
    "            'D': (1, 0),\n",
    "        }\n",
    "        for i in range(len(s)):\n",
    "            res.append(cal(startPos, n, s[i:]))\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n",
    "        move = {'L':(0,-1),'R':(0,1),'D':(1,0),'U':(-1,0)}\n",
    "\n",
    "        @cache\n",
    "        def f(s):\n",
    "            # print(s)\n",
    "            x,y = startPos\n",
    "            for i,c in enumerate(s):\n",
    "                x += move[c][0]\n",
    "                y += move[c][1]\n",
    "                if x < 0 or x >= n: return i\n",
    "                if y < 0 or y >= n: return i\n",
    "                # print(x,y)\n",
    "            return len(s)\n",
    "\n",
    "\n",
    "        ans = list(map(f,[s[i:] for i in range(len(s))]))\n",
    "        f.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n",
    "        res = []\n",
    "        tmps = list(s)\n",
    "        for j in range(len(s)):\n",
    "            #print(tmps)\n",
    "            tmpPos = startPos\n",
    "            for i in range(len(tmps)):\n",
    "                tmpPos = self.move(tmps[i], tmpPos)\n",
    "                #print(tmpPos)  \n",
    "                if tmpPos[0] < 0 or tmpPos[1] < 0 or tmpPos[0] > n - 1 or tmpPos[1] > n - 1 :\n",
    "                    res.append(i)\n",
    "                    #print(res)\n",
    "                    break\n",
    "                elif i == len(tmps) - 1:\n",
    "                    res.append(i + 1)\n",
    "                    #print(res)\n",
    "                    break\n",
    "            tmps.remove(tmps[0])\n",
    "        return res\n",
    "\n",
    "    def move(self, toward: str, startPos: List[int]) -> List[int]:\n",
    "        if toward == 'R':\n",
    "            return [startPos[0], startPos[1] + 1]\n",
    "        elif toward == 'L':\n",
    "            return [startPos[0], startPos[1] - 1]\n",
    "        elif toward == 'U':\n",
    "            return [startPos[0] - 1, startPos[1]]\n",
    "        elif toward == 'D':\n",
    "            return [startPos[0] + 1, startPos[1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n",
    "        res = []\n",
    "        loc = {'R':(0,1),'L':(0,-1),'U':(-1,0),'D':(1,0)}\n",
    "        while s:\n",
    "            y,x = startPos\n",
    "            for i,a in enumerate(s):\n",
    "                y += loc[a][0]\n",
    "                x += loc[a][1]\n",
    "                if x < 0 or x >= n or y < 0 or y >= n:\n",
    "                     break\n",
    "                else:\n",
    "                    i += 1\n",
    "            res.append(i)\n",
    "            s = s[1:]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n",
    "        ans = []\n",
    "        while s:\n",
    "            currentPos = startPos.copy()\n",
    "            for i, move in enumerate(s):\n",
    "                if move == \"R\":\n",
    "                    currentPos[1] += 1\n",
    "                if move == \"L\":\n",
    "                    currentPos[1] -= 1\n",
    "                if move == \"U\":\n",
    "                    currentPos[0] -= 1\n",
    "                if move == \"D\":\n",
    "                    currentPos[0] += 1\n",
    "                if (currentPos[0]==-1)or (currentPos[0]==n) or(currentPos[1]==-1)or (currentPos[1]==n):\n",
    "                    break\n",
    "                else:\n",
    "                    i += 1 \n",
    "            ans.append(i)\n",
    "            s = s[1:]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n",
    "        ans = []\n",
    "        while s:\n",
    "            currentPos = startPos.copy()\n",
    "            for i, move in enumerate(s):\n",
    "                if move == \"R\":\n",
    "                    currentPos[1] += 1\n",
    "                if move == \"L\":\n",
    "                    currentPos[1] -= 1\n",
    "                if move == \"U\":\n",
    "                    currentPos[0] -= 1\n",
    "                if move == \"D\":\n",
    "                    currentPos[0] += 1\n",
    "                if (currentPos[0]==-1)or (currentPos[0]==n) or(currentPos[1]==-1)or (currentPos[1]==n):\n",
    "                    break\n",
    "                else:\n",
    "                    i += 1 \n",
    "            ans.append(i)\n",
    "            s = s[1:]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n",
    "        ans = []\n",
    "        dir = {'L':(0,-1),'R':(0,1),'U':(-1,0),'D':(1,0)}\n",
    "        #print(f'{dir['L']}')\n",
    "        for i in range(len(s)):\n",
    "            x, y = startPos\n",
    "            cnt = 0\n",
    "            \n",
    "            for j in range(i, len(s)):\n",
    "                st = s[j]\n",
    "                if 0 <= x + dir[st][0] < n and 0 <= y + dir[st][1] < n:\n",
    "                    #print(f'{x,y}')\n",
    "                    x += dir[st][0]\n",
    "                    y += dir[st][1]\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    break\n",
    "            ans.append(cnt)\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOVE = {'R':(1, 0), 'L':(-1, 0), 'U':(0, -1), 'D':(0, 1)}\n",
    "\n",
    "class Solution:\n",
    "    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n",
    "        dx = Counter()\n",
    "        dy = Counter()\n",
    "        ans = [0] * len(s)\n",
    "        # 前往终点\n",
    "        y, x = startPos\n",
    "        for c in s:\n",
    "            x += MOVE[c][0]\n",
    "            y += MOVE[c][1]\n",
    "        # 倒着走\n",
    "        print(s[-1])\n",
    "        for i, c in enumerate(s[::-1], 1):\n",
    "            # dx与dy是当前时刻经过该线后的点的最大数量\n",
    "            print(i,c)\n",
    "            dx[x] = dy[y] = i\n",
    "            x -= MOVE[c][0]\n",
    "            y -= MOVE[c][1]\n",
    "            # x1，y1是边界的偏移量，是移动边界使当前点与初始点位置相同所需的偏移量\n",
    "            x1, y1 = x - startPos[1], y - startPos[0]    \n",
    "            # -1和n是原来的边界，加上偏移量变为新的边界，边界上最新的记录就是第一次越界时的记录\n",
    "            temp = max(dx[x1 - 1], dx[x1 + n], dy[y1 - 1], dy[y1 + n])\n",
    "            # temp为无法到达的点的数量\n",
    "            ans[-i] = i - temp\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOVE = {'R':(1, 0), 'L':(-1, 0), 'U':(0, -1), 'D':(0, 1)}\n",
    "\n",
    "class Solution:\n",
    "    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n",
    "        dx = Counter()\n",
    "        dy = Counter()\n",
    "        ans = [0] * len(s)\n",
    "        # 前往终点\n",
    "        y, x = startPos\n",
    "        for c in s:\n",
    "            x += MOVE[c][0]\n",
    "            y += MOVE[c][1]\n",
    "        # 倒着走\n",
    "        print(s[-1])\n",
    "        for i, c in enumerate(s[::-1], 1):\n",
    "            # dx与dy是当前时刻经过该线后的点的最大数量\n",
    "            print(i,c)\n",
    "            dx[x] = dy[y] = i\n",
    "            x -= MOVE[c][0]\n",
    "            y -= MOVE[c][1]\n",
    "            # x1，y1是边界的偏移量，是移动边界使当前点与初始点位置相同所需的偏移量\n",
    "            x1, y1 = x - startPos[1], y - startPos[0]    \n",
    "            # -1和n是原来的边界，加上偏移量变为新的边界，边界上最新的记录就是第一次越界时的记录\n",
    "            temp = max(dx[x1 - 1], dx[x1 + n], dy[y1 - 1], dy[y1 + n])\n",
    "            # temp为无法到达的点的数量\n",
    "            ans[-i] = i - temp\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOVE = {'R':(0, 1), 'L':(0, -1), 'U':(-1, 0), 'D':(1, 0)}\n",
    "\n",
    "class Solution:\n",
    "    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n",
    "        l = len(s)\n",
    "        ans = [0] * l\n",
    "        n -= 1\n",
    "        for i in range(l):\n",
    "            now = startPos.copy()\n",
    "            for c in s[i:]:\n",
    "                row, col = MOVE[c]\n",
    "                now[0] += row\n",
    "                now[1] += col\n",
    "                if now[1] < 0 or now[1] > n or now[0] < 0 or now[0] > n:\n",
    "                    break\n",
    "                ans[i] += 1\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
